Túc thừa (bị giới hạn ở N 2 {\displaystyle \mathbb {N} ^{2}} ) không phải là một hàm đệ quy cơ bản. Người ta có thể chứng minh bằng cảm ứng rằng với mọi hàm đệ quy sơ cấp f, có một hằng số c sao cho

f ( x ) ≤ 2 2 ⋅ ⋅ x ⏟ c . {\displaystyle f(x)\leq \underbrace {2^{2^{\cdot ^{\cdot ^{x}}}}} _{c}.}

Chúng ta biểu thị phía bên tay phải bởi g ( c , x ) {\displaystyle g(c,x)} . Giả sử ngược lại rằng túc thừa là đệ quy sơ cấp. g ( x , x ) + 1 {\displaystyle g(x,x)+1} cũng là đệ quy sơ cấp. Theo bất đẳng thức trên, có một hằng số c sao cho g ( x , x ) + 1 ≤ g ( c , x ) {\displaystyle g(x,x)+1\leq g(c,x)} . Bằng cách để x = c {\displaystyle x=c} , chúng ta có g ( c , c ) + 1 ≤ g ( c , c ) {\displaystyle g(c,c)+1\leq g(c,c)} , một mâu thuẫn.